package uestc.lj.basicPromotion.tree;

/**
 * 求二叉树中两节点的最大距离
 *
 * @Author:Crazlee
 * @Date:2021/11/27
 */
public class Code01_MaxDistance {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static class Info {
		public int maxDistance;
		public int height;

		public Info(int maxDistance, int height) {
			this.maxDistance = maxDistance;
			this.height = height;
		}
	}

	public static int maxDistance(Node root) {
		return process(root).maxDistance;
	}

	private static Info process(Node root) {
		if (root == null) {
			return new Info(0, 0);
		}
		Info left = process(root.left);
		Info right = process(root.right);
		int leftMaxDistance = left.maxDistance;
		int rightMaxDistance = right.maxDistance;
		int maxdistance = left.height + right.height + 1;
		int result = Math.max(maxdistance, Math.max(leftMaxDistance, rightMaxDistance));
		int height = Math.max(right.height, left.height) + 1;
		return new Info(result, height);
	}

}
